class Solution {
public:
    bool is_number(string str){
		if(str.length()==0){
			return false;
		}
		if(str[0] != '-'){
        	if(str[0] > 47 && str[0] < 58){
        	    return true;
        	}
			return false;
		}else if(str[0] == '-'){
			if(str.length() > 1){
				if(str[1] > 47 && str[1] < 58){
    	    	    return true;
    	    	}
			}
			return false;
		}
    }
    int convert_num(string str){
		if(str[0] != '-'){
        	int cand = 0;
        	int result = 0;
	        while(cand < str.length()){
    	        result = result*10 + str[cand]-48;
    	        cand++;
    	    }
			return result;
		}else{
			int cand = 1;
        	int result = 0;
	        while(cand < str.length()){
    	        result = result*10 - (str[cand]-48);
    	        cand++;
    	    }
			return result;	
		}
        
    }
    string convert_string(int num){
        string result = "";
        if(num == 0){
            return "0";
        }
		if(num > 0){
	        while(num > 0){
	            string new_str = " ";
	            new_str[0] = num%10 + 48;
	            result = new_str.append(result);
	            num = num/10;
	        }
			return result;
		}else{
			num = 0-num;
			while(num > 0){
	            string new_str = " ";
	            new_str[0] = num%10 + 48;
	            result = new_str.append(result);
	            num = num/10;
			}
			string extra = "-";
			return extra.append(result);
		}
    }
	typedef struct{
		int next;
		int prev;
	}node;
    int evalRPN(vector<string> &tokens) {
        if(tokens.size()==1){
            return convert_num(tokens[0]);
        }
		node index_list[tokens.size()];
		for(int i=0; i<tokens.size(); i++){
			index_list[i].prev = i-1;
			index_list[i].next = i+1;
		}
		int itf = 0;
        int its = 1;
        int ito = 2;
		int result;
		while(ito < tokens.size()){
        
        while(tokens[ito] != "+" && tokens[ito] != "-"
				&& tokens[ito] != "*" && tokens[ito] != "/"){
            ito = index_list[ito].next;
        }
        its = index_list[ito].prev;
		while(!is_number(tokens[its])){
			its = index_list[its].prev;
		}
		itf = index_list[its].prev;
		while(!is_number(tokens[itf])){
			itf = index_list[itf].prev;
		}
        int f = convert_num(tokens[itf]);
        int s = convert_num(tokens[its]);
        if(tokens[ito] == "+"){
            result = f + s;
        }else if(tokens[ito] == "-"){
            result = f - s;
        }else if(tokens[ito] == "*"){
            result = f * s;
        }else if(tokens[ito] == "/"){
            result = f / s;
        }
        tokens[itf] = "";
		index_list[index_list[itf].prev].next = index_list[itf].next;
		index_list[index_list[itf].next].prev = index_list[itf].prev;
		tokens[its] = "";
		index_list[index_list[its].prev].next = index_list[its].next;
		index_list[index_list[its].next].prev = index_list[its].prev;
        tokens[ito] = convert_string(result);

		ito = index_list[ito].next;
		}
        return result;
    }
};
